package com.markbuikema.da.opdr1;

/**
 * @author Mark
 * 
 */
public class Main {

	public static void main(String[] args) {
		execute(1, 10, 5000);
		execute(1, 10, 10000);
		execute(1, 10, 20000);
		execute(1, 10, 50000);
		execute(1, 10, 100000);
		execute(2, 10, 100000);
		execute(2, 10, 500000);
		execute(2, 10, 1000000);
		execute(2, 10, 5000000);
		execute(2, 10, 10000000);
		execute(3, 10, 5000000);
		execute(3, 10, 10000000);
		execute(3, 10, 20000000);
		execute(3, 10, 40000000);
		execute(3, 10, 80000000);
	}

	/**
	 * Executes the passed algorithm count times with length as input.
	 * 
	 * @param algorithm
	 *            The number of the algorithm. Must be either 1, 2 or 3.
	 * @param count
	 *            How many times the algorithm should be executed in order to
	 *            get an accurate average duration
	 * @param length
	 *            The length of the array to create
	 */
	public static void execute(int algorithm, int count, int length) {
		long[] durations = new long[count];
		switch (algorithm) {
		case 1:
			for (int i = 0; i < count; i++)
				durations[i] = algorithm1(length).getDuration();
			break;
		case 2:
			for (int i = 0; i < count; i++)
				durations[i] = algorithm2(length).getDuration();
			break;
		case 3:
			for (int i = 0; i < count; i++)
				durations[i] = algorithm3(length).getDuration();
			break;
		default:
			System.out.println("Invalid algorithm");
			return;
		}

		int durationSum = 0;
		for (int i = 0; i < durations.length; i++) {
			durationSum += durations[i];
		}
		int averageDuration = count == 0 ? 0 : durationSum / count;
		System.out.println("Executed algorithm " + algorithm + " " + count + " times with N = " + length + ", took " + averageDuration
				+ " ms on average.");
	}

	/**
	 * Creates an array with unique numbers from 0 to length-1 in a random
	 * order. Generates a random number until a number has been found that is
	 * not yet in the array. That number will then be added.
	 * 
	 * @param length
	 *            The length of the array to create
	 * @return An AlgorithmOutput object that contains the results of the
	 *         algorithm execution.
	 */
	public static AlgorithmOutput algorithm1(int length) {

		long startTime = System.currentTimeMillis();

		int[] output = new int[length];

		for (int i = 0; i < length; i++) {
			boolean contains;
			int number;
			do {
				contains = false;
				number = randInt(0, length - 1);
				for (int j = 0; j < i; j++) {
					// timeout if necessary
					if (System.currentTimeMillis() > startTime + 1000 * 60) {
						AlgorithmOutput result = new AlgorithmOutput(10000 * 60, null, 1, length);
						System.out.println(result);
						return result;
					}

					// check if number is in the array
					if (output[j] == number) {
						contains = true;
						break;
					}
				}
			} while (contains);

			output[i] = number;
		}

		long duration = System.currentTimeMillis() - startTime;

		AlgorithmOutput result = new AlgorithmOutput(duration, output, 1, length);
		// System.out.println(result);
		return result;
	}

	/**
	 * Creates an array with unique numbers from 0 to length-1 in a random
	 * order. Stores which numbers have been used in an extra array. Generates a
	 * random number until a number was not used according to the extra array.
	 * 
	 * @param length
	 *            the length of the array to create.
	 * @return An AlgorithmOutput object that contains the results of the
	 *         algorithm execution.
	 */
	public static AlgorithmOutput algorithm2(int length) {

		long startTime = System.currentTimeMillis();

		boolean[] used = new boolean[length];
		int[] output = new int[length];
		for (int i = 0; i < output.length; i++) {
			int number;
			do {
				// timeout if necessary
				if (System.currentTimeMillis() > startTime + 1000 * 60) {
					AlgorithmOutput result = new AlgorithmOutput(10000 * 60, null, 2, length);
					System.out.println(result);
					return result;
				}
				// assign the number to the array
				number = randInt(0, used.length - 1);
			} while (used[number]);
			used[number] = true;
			output[i] = number;
		}

		long duration = System.currentTimeMillis() - startTime;

		AlgorithmOutput result = new AlgorithmOutput(duration, output, 2, length);
		// System.out.println(result);
		return result;
	}

	/**
	 * Creates an array of unique numbers from 0 to length-1 in a random order.
	 * Assigns the index of the value as the value and then swaps numbers
	 * randomly.
	 * 
	 * @param length
	 *            the length of the array to create.
	 * @return An AlgorithmOutput object that contains the results of the
	 *         algorithm execution.
	 */
	public static AlgorithmOutput algorithm3(int length) {

		long startTime = System.currentTimeMillis();

		int[] output = new int[length];
		for (int i = 0; i < output.length; i++) {
			output[i] = i;
		}
		for (int i = 0; i < output.length; i++) {
			// timeout if necessary
			if (System.currentTimeMillis() > startTime + 1000 * 60) {
				AlgorithmOutput result = new AlgorithmOutput(10000 * 60, null, 3, length);
				System.out.println(result);
				return result;
			}

			// swap number with a random other number
			int randomIndex = randInt(0, length - 1);

			int currentNumber = output[i];
			int newNumber = output[randomIndex];

			output[randomIndex] = currentNumber;
			output[i] = newNumber;
		}

		long duration = System.currentTimeMillis() - startTime;

		AlgorithmOutput result = new AlgorithmOutput(duration, output, 3, length);
		// System.out.println(result);
		return result;
	}

	public static int randInt(int min, int max) {
		return (int) (Math.random() * (max - min + 1) + min);
	}

}
